package 二分查找.easy;

/**
 * 1. 问题描述
 *      从有序的数组中返回指定元素的索引下标，如果没有找到，返回-1
 *
 * 2. 算法分析
 *      此题是一个最简单的二叉查找的案例，虽然简单，但是其中有许多细节值得我们去注意
 *      下面我们主要分析一下在写二分查找的代码时的一些注意事项：
 *      我们先附上代码：
 *          int left = 0;
 *          int right = arr.length - 1;
 *          while (left <= right) {
 *             int mid = left + (right - left) / 2;
 *             if (arr[mid] == target) {
 *                 return mid;
 *             }
 *             if (arr[mid] < target) {
 *                 left = mid + 1;
 *             } else {
 *                 right = mid - 1;
 *             }
 *          }
 *          return -1;
 *      1. left和right指针的确定
 *          left肯定为0，但是right为什么取arr.length-1，而不是arr.length
 *          这是由于数组的索引恰好到arr.length-1,我们考虑[left,right],如果
 *          right选择的是arr.length，实际上这个是一个左闭右开的区间，但是选择
 *          arr.length-1就是一个闭区间
 *
 *      2. 循环退出的条件 到底是left < right 还是 left <= rigth
 *         试想，如果退出的条件为left < right，此时当left = right是退出循环，但是
 *         我们就遗漏了当前这种情况，所以退出的条件因该为left <= right
 *
 *      3. mid的计算方式
 *         为什么mid = left + (right - left) / 2而不是mid = (left + right) / 2
 *         第一种而言为left向右移动了(right-left)/2个单位，而第二种方法是直接赋值。对于
 *         数字计算而言两者没有任何问题，但是对于计算机的除法运算是会出现问题的
 *
 *      4. 如果数组中有重复元素例如 arr = {1，2，3，3，4，5，6，7},但是此时我们向返回第一个3的索引
 *         此时上述的判断的代码是有问题的
 *         那么我们如何修改上述的代码，让我们始终返回的是第一次该元素出现的索引下标
 *         我们通过具体的例子来看 arr = {1，2，3，3，4，5，6，7}  target = 3
 *         1. left = 0   right = 7 初始   mid = left + (right - left) / 2 = 3
 *            arr[3] = 3  此时直接返回 3， 但是这并不是我们想要的哪一个3，我们想要的索引
 *            因该为2
 *         此时该如何解决呢?
 *         1. 由于是有序的数组，当我们找到目标元素之后向前遍历到该元素第一次出现的位置即可
 *
 *     5. 对于 mid 的优化计算
 *          我们可以利用位运算来计算mid(增补码)
 *          mid = left + (right-left) >> 1
 *          a >> m  a = 1/2^m   a << m   a = 2 ^ m
 *
 *
 */
@SuppressWarnings("all")
public class 经典的二分查找 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,3,4,4,4,5,5,5,6,8,9};
        System.out.println(binarySearch2(arr,5));
    }

    /**
     * 二分查找
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearch(int[] arr,int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            }
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 优化
     *  找到目标元素第一次出现的索引
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearch2(int[] arr,int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                while (mid >= 0) {
                    if (arr[mid] != target) {
                        break;
                    }
                    mid--;
                }
                return mid+1;
            }
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}
